package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * description:
 * author:张腾
 * date:2021-06-06
 */

/**
 * 已知中序遍历和后序遍历，求树
 */
public class leetcode106 {
    Map<Integer,Integer> map = new HashMap<>();
    int[] postOrder;

    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        this.postOrder = postorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return build2(0,inorder.length-1,0,postorder.length-1);
    }

    public TreeNode build2(int inL,int inR,int postL,int postR){
        if (inL>inR || postL>postR) return null;

        TreeNode root = new TreeNode(postOrder[postR]);
        int index = map.get(postOrder[postR]);

        root.left = build2(inL,index-1,postL,postL+index-inL-1);
        root.right = build2(index+1,inR,postL+index-inL,postR-1);

        return root;
    }

}
